package com.hyb.algorithm.data.struct.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: ybhu
 * @create: 2021/08/22 22:39
 * <p>
 * https://leetcode-cn.com/problems/super-egg-drop/
 * 887. 鸡蛋掉落
 */
public class SuperEggDrop {

    public static void main(String[] args) {

    }

    Map<Integer, Integer> map = new HashMap<>();


    /**
     * 计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
     *
     * @param k
     * @param n
     * @return
     */
    public int superEggDrop(int k, int n) {

        return dpEgg(k, n);
    }


    /**
     * k 个鸡蛋   n 层楼
     *
     * @param k
     * @param n
     * @return
     */
    public int dpEgg2(int k, int n) {


        // 0层楼
        if (n == 0) {
            return 0;
        }

        //一个鸡蛋的时候
        if (k == 1) {
            return n;
        }

        int mapKey = n * 1000 + k;

        if (map.containsKey(mapKey)) {
            return map.get(mapKey);
        }

        int low = 1;
        int hi = n;

        int ret = 0;

        while (low + 1 < hi) {

            int mid = low + (hi - low) / 2;

            //不破
            int t2 = dpEgg(k, n - mid);

            //破了
            int t1 = dpEgg(k - 1, mid - 1);

            // 图中交点的左边
            if (t1 < t2) {
                low = mid;
                // 图中交点的右边边
            } else if (t1 > t2) {
                hi = mid;
            } else {
                low = hi = mid;
            }

        }

        ret = 1 + Math.min(Math.max(dpEgg(k - 1, low - 1), dpEgg(k, n - low)),
                Math.max(dpEgg(k - 1, hi - 1), dpEgg(k, n - hi)));
        map.put(mapKey, ret);
        return ret;

    }


    /**
     * k 个鸡蛋   n 层楼
     *
     * @param k
     * @param n
     * @return
     */
    public int dpEgg1(int k, int n) {


        // 0层楼
        if (n == 0) {
            return 0;
        }

        //一个鸡蛋的时候
        if (k == 1) {
            return n;
        }

        int mapKey = n * 1000 + k;

        if (map.containsKey(mapKey)) {
            return map.get(mapKey);
        }

        int low = 1;
        int hi = n;

        int ret = Integer.MAX_VALUE;

        while (low <= hi) {

            int mid = low + (hi - low) / 2;

            //不破
            int broken = dpEgg(k - 1, mid - 1);

            //破了
            int noBroken = dpEgg(k, n - mid);

            // 图中交点的左边  左边移动
            if (broken < noBroken) {
                low = mid + 1;
                // 图中交点的右边边
                ret = Math.min(ret, noBroken + 1);
            } else {
                hi = mid - 1;
                ret = Math.min(ret, broken + 1);
            }

        }
        map.put(mapKey, ret);
        return ret;

    }


    /**
     * k 个鸡蛋   n 层楼
     * <p>
     * dp[k][m] = n
     * # 当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
     * # 这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
     * <p>
     * # 比如说 dp[1][7] = 7 表示：
     * # 现在有 1 个鸡蛋，允许你扔 7 次;
     * # 这个状态下最多给你 7 层楼，
     * # 使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
     * # （一层一层线性探查嘛）
     * dp[K][m] == N，也就是给你 K 个鸡蛋，测试 m 次，最坏情况下最多能测试 N 层楼。
     *
     * @param k
     * @param n
     * @return
     */
    public int dpEgg(int k, int n) {

        int[][] dp = new int[k + 1][n + 1];

        int m = 0;
        for (int i = 0; dp[k][m] < n; i++) {
            m++;
            for (int j = 0; j < k; j++) {
                dp[j][m] = dp[j - 1][m - 1] + dp[j][m - 1] + 1;
            }
        }

        return m;
    }

}
